// ----------------------------------------------------------------------------
// radix_sort.h
// ----------------------------------------------------------------------------
/*
 Description:
 レンダリング処理のための基数ソートの実装.
 
 ----------------------------------------------------------------
 使い方.
 
 .
 */
#pragma once

namespace fw
{
    // (FW_RADIX_SORT_BITS)bitずつでキーを分類する.
    #define FW_RADIX_SORT_BITS              (11)
    #define FW_RADIX_SORT_HISTOGRAM_SIZE    (1<<FW_RADIX_SORT_BITS)
    #define FW_RADIX_SORT_BIT_MASK          (FW_RADIX_SORT_HISTOGRAM_SIZE-1)
    
    //! 32bitもしくは64bitの基数ソート. 値として扱われるT型はコピー可能であること.
    template <typename B, typename T> void RadixSort(B* __restrict _keys, B* __restrict _tempKeys, T* __restrict _values, T* __restrict _tempValues, size_t _size)
    {
        B* __restrict keys          = _keys;
        B* __restrict tempKeys      = _tempKeys;
        T* __restrict values        = _values;
        T* __restrict tempValues    = _tempValues;
        
        uint16_t histogram[FW_RADIX_SORT_HISTOGRAM_SIZE];
        uint16_t shift = 0;
        uint32_t pass  = 0;
        uint32_t loopCount  = (3 * sizeof(B)) / sizeof(uint32_t); // B = uint32_t or uint64_t
        
        for(; pass<loopCount; ++pass)
        {
            memset(histogram, 0, sizeof(uint16_t)*FW_RADIX_SORT_HISTOGRAM_SIZE);
            
            bool sorted  = true;
            B    key     = keys[0];
            B    prevKey = key;
            
            for(size_t ii=0; ii<_size; ++ii, prevKey=key)
            {
                key = keys[ii];
                uint16_t index = (key>>shift) & FW_RADIX_SORT_BIT_MASK;
                ++histogram[index];
                sorted &= prevKey <= key;
            }
            
            if(sorted)
            {
                goto done;
            }
            
            uint16_t offset = 0;
            for(size_t ii=0; ii<FW_RADIX_SORT_HISTOGRAM_SIZE; ++ii)
            {
                uint16_t count = histogram[ii];
                histogram[ii] = offset;
                offset += count;
            }
            
            for(size_t ii=0; ii<_size; ++ii)
            {
                B           key     = keys[ii];
                uint16_t    index   = (key>>shift) & FW_RADIX_SORT_BIT_MASK;
                uint16_t    dest    = histogram[index]++;
                tempKeys  [dest]    = key;
                tempValues[dest]    = values[ii];
            }
            
            B* swapKeys     = tempKeys;
            tempKeys        = keys;
            keys            = swapKeys;
            
            T* swapValues   = tempValues;
            tempValues      = values;
            values          = swapValues;
            
            shift += FW_RADIX_SORT_BITS;
        }
        
    done:
        if((pass & 1)!=0)
        {   // 奇数のときは元のバッファに対して値を書き戻す.
            memcpy(_keys, _tempKeys, sizeof(B) * _size);
            for(size_t ii=0; ii<_size; ++ii)
            {
                _values[ii] = _tempValues[ii];
            }
        }
    } // RadixSort
    
    
} // namespace fw


